// 编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

// 示例 :

// 输入: 11
// 输出: 3
// 解释: 整数 11 的二进制表示为 00000000000000000000000000001011
 

// 示例 2:

// 输入: 128
// 输出: 1
// 解释: 整数 128 的二进制表示为 00000000000000000000000010000000

#include "stdc++.h"

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int res{0};
        while (n) {
            ++res;
            n &= n-1; // 把最右边的1删掉
        }
        return res;
    }
};

/*
进阶：
    如果多次调用这个函数，你将如何优化你的算法？
*/
class Solution {
public:
    int hammingWeight(uint32_t n) {
        if (hash.find(n) == hash.end()) {
            int num{0};
            uint32_t temp{n};
            while (temp) {
                temp = temp & (temp - 1);
                ++num;
            }
            hash[n] = num;
        }
        return hash[n];
    }
private:
    unordered_map<uint32_t, int> hash{};
};